/*
 jChecs: a Java chess game sample 

 Copyright (C) 2006-2011 by David Cotton

 This program is free software; you can redistribute it and/or modify it under
 the terms of the GNU General Public License as published by the Free Software
 Foundation; either version 2 of the License, or (at your option) any later
 version.

 This program is distributed in the hope that it will be useful, but WITHOUT
 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

 You should have received a copy of the GNU General Public License along with
 this program; if not, write to the Free Software Foundation, Inc., 51 Franklin
 Street, Fifth Floor, Boston, MA 02110-1301, USA.
 */
package fr.free.jchecs.ai;

import java.util.Arrays;
import java.util.Comparator;

import fr.free.jchecs.core.Move;
import fr.free.jchecs.core.MoveGenerator;

/**
 *	AI engine using AlphaBeta algorithm with max search depth 5.
 * 
 * @author Michael Silva
 *
 */
final class AlphaBetaEngine extends AbstractEngine {
	/**
	 * Create a new instance of the AlphaBeta engine.
	 */
	AlphaBetaEngine() {
		
			// Sets values used in GUI. Has no impact on tests. [Silva]
		super(3, 6, 5);
		
			// jChecs provides different ways to sort moves.  This represent
			// improvements on AlphaBeta, but I have chosen not to use
			// them. [Silva]
		setMoveSorter(new StaticMoveSorter());
	}

	
	/**
	 * Implementation of the AlphaBeta algorithm.
	 * 	Implementation is based on pseudo-code in "Algorithms in a Nutshell" 
	 * 
	 * @param pState
	 * 						State of the board.
	 * @param pDepth
	 * 						Depth of the current search.
	 * @param pAlpha
	 * 						Alpha threshold.
	 * @param pBeta
	 * 						Beta threshold.
	 * @return Best move at this level
	 */
	private int alphabeta (final MoveGenerator pState, final int pDepth,
												final int pAlpha, final int pBeta)
	{
			// Assertions for debugging
		assert pState != null; assert pDepth >=0; assert pAlpha <= pBeta;
		
			// Determine current player. Black is False, White is True.
		final boolean color = pState.isWhiteActive();
		
			// Reached max search depth or no moves remaining: Eval board.
		if (pDepth == 0 || pState.getValidMoves(color).length == 0){
			return getHeuristic().evaluate(pState, color);
		}
		
			// Declarations for readability
		int best = MATE_VALUE - 1, alpha = pAlpha;
		final Move[] moveList = pState.getValidMoves(color);
		
			// Used for updating jChec's move counter.
		addHalfmove(moveList.length);
		
			// Perform the work.
		for (final Move move : moveList){
				// The recurrsive call
			final int responseValue = 
					- (alphabeta(pState.derive(move,true),pDepth-1,-pBeta,-alpha));
			
				// Good move?
			if (responseValue > best){
					// Yes!
				best = responseValue;
				if (alpha > pBeta) {
					return best;
				}
			}
		}
	
		return best;
	}
		

	/**
	 * Design of jChecs requires the first level of moves be inspected
	 * by the searchMoveFor function, rather than using a single AI function.
	 * 
	 * @param pState
	 * 
	 * @param moveList
	 */
	protected Move searchMoveFor(final MoveGenerator pState, final Move[] moveList)
	{
			// Assertions for debugging
		assert pState != null; assert moveList != null;
		
			// Used for updating jChec's move counter.
		assert moveList.length > 0;
		addHalfmove(moveList.length);
		
			// Perform the work
		int alpha = MATE_VALUE - 1;
		Move best = moveList[0];
		for (final Move move : moveList) {
			final int responseValue = 
					- alphabeta(pState.derive(move,true), 				// State
											getSearchDepthLimit() - 1, 	// Ply
											MATE_VALUE, -alpha);		// Alpha, Beta
				// Good move?
			if (responseValue > alpha){
					// Yes!
				alpha = responseValue;
				best = move;	
			}
		}
		
		setScore(alpha);

		assert best != null;
		return best;
		
	}
}
